/*
题目：树的子结构
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。
https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof/
 */
public class Offer26 {
    public boolean isAPart(TreeNode A, TreeNode B) {
        if (B == null) return true;//如果B为空，说明B可能是A的一部分了
        if (A == null) return false;//A为空，则匹配过头
        if (A.val != B.val) return false;
        return isAPart(A.left, B.left) && isAPart(A.right, B.right);
    }

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;//其中一个是空，都不满足题意
        return isAPart(A,B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
}
